# 499. 子串分值(好题, 贡献算法)
# https://www.lanqiao.cn/problems/1498/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/18
from collections import Counter


def count_once_char_bf(inp_str: str):
    """
    暴力解法,枚举每个字串.
    超时/正常=6/4
    """
    n = len(inp_str)
    res = 0
    for start in range(n):
        for length in range(1, n - start + 1):
            substr = inp_str[start: start + length]
            res += Counter(Counter(substr).values()).get(1, 0)
    return res


def count_once_char_contribution(inp_str: str):
    """贡献法：从枚举的思路改为每个元素能为总和贡献多少,跟贪心一样是一种思想,没有固定的模板和套路,只能因题而异.
    对于本题来说我们可以计算每个字符贡献的分值, 计算每个字符的贡献分值之和就是结果.
    例如下面一个字符串
    a x x a x x x a
    0     3       7
    那么在[1, 6]这个区间中的任意包含中间"a"的子串, 都会为最后的分值贡献1
    即 (xxa) (xxax) (xxaxx) (xxaxxx) (xa) (xax) (xaxx) (xaxxx) (a) (ax) (axx) (axxx) 这12种组合的贡献值都为1
    所以, 这个a的贡献总值就是 (3 - 0) * (7 - 3) = 12
    对于第一个"a"来说, 在[0,2]这个区间的包含"a"的任意子串, 贡献值也是1, 也就是 1 * 3
    """
    n = len(inp_str)
    res = 0

    for i, c in enumerate(inp_str):
        left, right = i - 1, i + 1
        while left >= 0 and inp_str[left] != c:
            left -= 1
        while right < n and inp_str[right] != c:
            right += 1
        res += (i - left) * (right - i)

    return res


if __name__ == '__main__':
    # ababc -> (a)1 (b)1 (a)1 (b)1 (c)1 (ab)2 (ba)2 (ab)2 (bc)2 (aba)1 (bab)1 (abc)3 (abab)0 (babc)2 (ababc)1 -> 21
    print(count_once_char_bf("ababc"))
    print(count_once_char_contribution("ababc"))  # a:
